package rank1400;

import java.util.Arrays;

/**
 * 1508. 子数组和排序后的区间和
 */
public class No1508 {

    public int rangeSum(int[] nums, int n, int left, int right) {
        int[] path = new int[n * (n + 1) / 2];
        int ans = 0, index = 0;
        for (int i = 0; i < n; i++) {
            int curSum = 0;
            for (int j = i; j < n; j++) {
                curSum += nums[j];
                path[index++] = curSum;
            }
        }
        Arrays.sort(path);
        for (int i = left - 1; i < right; i++) {
            ans += path[i];
            ans %= (int) (1e9 + 7);
        }
        return ans;
    }
}
